package n3264;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int len=(int)(Math.log(50000)/Math.log(2));
	static int Max[][]=new int[50000][len+1];
	static int Min[][]=new int[50000][len+1];
	static int arr[]=new int[50000];
	
	static void init()
	{
		for(int i=0;i<N;i++)
		{
			Max[i][0]=i;
			Min[i][0]=i;
		}
		
		for(int i=1;(1<<i)<=N;i++)
			for(int j=0;(1<<i)+j-1<N;j++)
			{
				if(arr[Max[j][i-1]]<arr[Max[(1<<i-1)+j][i-1]])
				{
					Max[j][i]=Max[(1<<i-1)+j][i-1];
				}else{
					Max[j][i]=Max[j][i-1];
				}
				
				if(arr[Min[j][i-1]]>arr[Min[(1<<i-1)+j][i-1]])
				{
					Min[j][i]=Min[(1<<i-1)+j][i-1];
				}else{
					Min[j][i]=Min[j][i-1];
				}
			}
	}
	
	static int query(int l,int r)
	{
		if(l==r)return 0;
		int k=(int)(Math.log(r-l+1)/Math.log(2));
		int max=Math.max(arr[Max[l][k]], arr[Max[r-(1<<k)+1][k]]);
		int min=Math.min(arr[Min[l][k]], arr[Min[r-(1<<k)+1][k]]);
		return max-min;
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception{

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		N=Integer.parseInt(st.nextToken());
		int n=Integer.parseInt(st.nextToken());
		for(int i=0;i<N;i++)
		{
			arr[i]=Integer.parseInt(bf.readLine());
		}
		init();
		for(int i=0;i<n;i++)
		{
			st=new StringTokenizer(bf.readLine());
			int l=Integer.parseInt(st.nextToken());
			int r=Integer.parseInt(st.nextToken());
			System.out.println(query(l-1, r-1));
		}
	}

}
